Алгоритмы интеллектуальной обработки больших объемов данных

Домашнее задание №2: Линейные модели

<hr>

Общая информация

Срок сдачи: 05 апреля 18:00 Сдача очная на онлайн занятии. <br>

Используйте данный Ipython Notebook при оформлении домашнего задания.

Присылать ДЗ необходимо в виде ссылки на свой github репозиторий на почту ml1.sphere@mail.ru с указанием темы в следующем формате:

[ML0920, Задание 2] Фамилия Имя.

Штрафные баллы:

  1. Невыполнение PEP8 -1 балл
  2. Отсутствие фамилии в имени скрипта (скрипт должен называться по аналогии со stroykova_hw2.ipynb) -1 балл
  3. Все строчки должны быть выполнены. Нужно, чтобы output команды можно было увидеть уже в git'е. В противном случае -1 балл
  4. При оформлении ДЗ нужно пользоваться данным файлом в качестве шаблона. Не нужно удалять и видоизменять написанный код и текст, если явно не указана такая возможность. В противном случае -1 балл <hr>

Здравствуйте, уважаемые студенты!

В этом задании мы будем реализовать линейные модели. Необходимо реализовать линейную и логистическую регрессии с L2 регуляризацией

Теоретическое введение

Линейная регрессия решает задачу регрессии и оптимизирует функцию потерь MSE

$$L(w) = \frac{1}{N}\left[\sum_i (y_i - a_i) ^ 2 \right], $$

где $y_i$ $-$ целевая функция, $a_i = a(x_i) = \langle\,x_i,w\rangle ,$ $-$ предсказание алгоритма на объекте $x_i$, $w$ $-$ вектор весов (размерности $D$), $x_i$ $-$ вектор признаков (такой же размерности $D$).

Не забываем, что здесь и далее мы считаем, что в $x_i$ есть тождественный вектор единиц, ему соответствует вес $w_0$.

Логистическая регрессия является линейным классификатором, который оптимизирует так называемый функционал log loss:

$$L(w) = - \frac{1}{N}\left[\sum_i y_i \log a_i + ( 1 - y_i) \log (1 - a_i) \right],$$

где $y_i \in \{0,1\}$ $-$ метка класса, $a_i$ $-$ предсказание алгоритма на объекте $x_i$. Модель пытается предсказать апостериорую вероятность объекта принадлежать к классу "1": $$ p(y_i = 1 | x_i) = a(x_i) = \sigma( \langle\,x_i,w\rangle ),$$ $w$ $-$ вектор весов (размерности $D$), $x_i$ $-$ вектор признаков (такой же размерности $D$).

Функция $\sigma(x)$ $-$ нелинейная функция, пероводящее скалярное произведение объекта на веса в число $\in (0,1)$ (мы же моделируем вероятность все-таки!)

$$\sigma(x) = \frac{1}{1 + \exp(-x)}$$

Если внимательно посмотреть на функцию потерь, то можно заметить, что в зависимости от правильного ответа алгоритм штрафуется или функцией $-\log a_i$, или функцией $-\log (1 - a_i)$.

Часто для решения проблем, которые так или иначе связаны с проблемой переобучения, в функционал качества добавляют слагаемое, которое называют регуляризацией. Итоговый функционал для линейной регрессии тогда принимает вид:

$$L(w) = \frac{1}{N}\left[\sum_i (y_i - a_i) ^ 2 \right] + \frac{1}{C}R(w) $$

Для логистической: $$L(w) = - \frac{1}{N}\left[\sum_i y_i \log a_i + ( 1 - y_i) \log (1 - a_i) \right] + \frac{1}{C}R(w)$$

Самое понятие регуляризации введено основателем ВМК академиком Тихоновым https://ru.wikipedia.org/wiki/Метод_регуляризации_Тихонова

Идейно методика регуляризации заключается в следующем $-$ мы рассматриваем некорректно поставленную задачу (что это такое можно найти в интернете), для того чтобы сузить набор различных вариантов (лучшие из которых будут являться переобучением ) мы вводим дополнительные ограничения на множество искомых решений. На лекции Вы уже рассмотрели два варианта регуляризации.

$L1$ регуляризация: $$R(w) = \sum_{j=1}^{D}|w_j|$$ $L2$ регуляризация: $$R(w) = \sum_{j=1}^{D}w_j^2$$

С их помощью мы ограничиваем модель в возможности выбора каких угодно весов минимизирующих наш лосс, модель уже не сможет подстроиться под данные как ей угодно.

Вам нужно добавить соотвествущую Вашему варианту $L2$ регуляризацию.

И так, мы поняли, какую функцию ошибки будем минимизировать, разобрались, как получить предсказания по объекту и обученным весам. Осталось разобраться, как получить оптимальные веса. Для этого нужно выбрать какой-то метод оптимизации.

Градиентный спуск является самым популярным алгоритмом обучения линейных моделей. В этом задании Вам предложат реализовать стохастический градиентный спуск или мини-батч градиентный спуск (мини-батч на русский язык довольно сложно перевести, многие переводят это как "пакетный", но мне не кажется этот перевод удачным). Далее нам потребуется определение эпохи. Эпохой в SGD и MB-GD называется один проход по всем объектам в обучающей выборки.

Теоретические вопросы (2 балла)

В этой части Вам будут предложены теоретичские вопросы и задачи по теме. Вы, конечно, можете списать их у своего товарища или найти решение в интернете, но учтите, что они обязательно войдут в теоретический коллоквиум. Лучше разобраться в теме сейчас и успешно ответить на коллоквиуме, чем списать, не разобравшись в материале, и быть терзаемым совестью.

Формулы надо оформлять в формате LaTeX.

Задача 1. Градиент для линейной регрессии.

$$ w_{new} = w_{old} - ... $$

Отнеситесь к этому пункту максимально серьезно, это Вам нужно будет реализовать в задании.

Проанализруйте итоговую формулу градиента - как интуитивно можно описать, чему равен градиент?

Ваше решение здесь

$$\nabla_w(L(w)) = \nabla_w\left(\frac{1}{N}\sum_{i=1}^N{(x_iw - y_i)^2} + \frac{1}{C}\sum_{j=1}^D{w_j^2}\right) = \frac{2}{N}\sum_{i=1}^N{(x_iw - y_i)x_i^T} + \frac{2}{C}w$$$$w_{new} = w_{old} - \alpha\nabla_w(L(w)) = w_{old} - \alpha\left(\frac{2}{n}\sum_{i=1}^n{(x_iw_{old}-y_i)x_i^T} + \frac{2}{C}w_{old}\right)$$

Задача 2. Градиент для логистической регрессии.

$$ w_{new} = w_{old} - ... $$

Отнеситесь к этому пункту максимально серьезно, это Вам нужно будет реализовать в задании.

Проанализруйте итоговую формулу градиента - как интуитивно можно описать, чему равен градиент? Как соотносится этот градиент с градиентом, возникающий в задаче линейной регрессии?

Подсказка: Вам градиент, которой получается если “в лоб” продифференцировать, надо немного преобразовать. Надо подставить, что $1 - \sigma(w,x) $ это $1 - a(x_i)$, а $-\sigma(w,x)$ это $0 - a(x_i)$. Тогда получится свести к одной красивой формуле с линейной регрессией, которую программировать будет намного проще.

Ваше решение здесь

$$\nabla_w\left(L(w)\right) = \nabla_w\left(-\frac{1}{N}\sum_{i=1}^N{\left[y_i\log{\frac{1}{1 + e^{-x_iw}}} + (1 - y_i)\log{\frac{e^{-x_iw}}{1 + e^{-x_iw}}}\right]} + \frac{1}{C}\sum_{j=1}^D{w_j^2}\right) = $$$$ = \nabla_w\left(\frac{1}{N}\sum_{i=1}^N{\left[y_i\log{(1 + e^{-x_iw})} + (1 - y_i)\log{(1 + e^{x_iw})}\right]} + \frac{1}{C}w^Tw\right) = $$$$ = \frac{1}{N}\sum_{i=1}^N{\left[y_i\frac{-x_i^T}{1 + e^{x_iw}} + (1 - y_i)x_i^T\frac{e^{x_iw}}{1 + e^{x_iw}}\right]} + \frac{2}{C}w =$$$$ = \frac{1}{N}\sum_{i=1}^N\left[\frac{1}{1 + e^{-x_iw}} - y_i\right]x_i^T + \frac{2}{C}w = \frac{1}{N}\sum_{i=1}^N\left[\sigma(x_iw) - y_i\right]x_i^T + \frac{2}{C}w$$$$ w_{new} = w_{old} - \alpha\nabla_w(L(w)) = w_{old} - \alpha\left[\frac{1}{n}\sum_{i=1}^n\left[\sigma(x_iw_{old}) - y_i\right]x_i^T + \frac{2}{C}w_{old}\right]$$

Задача 3. Точное решение линейной регрессии

На лекции было показано, что точное решение линейной регрессии имеет вид $w = (X^TX)^{-1}X^TY $.

Ваше решение здесь

$$\nabla_w(\nabla_w(Q(w))) = 2 X^T X $$

По определению, матрица $A$ положительно определена, если $ \forall x \neq \theta \langle Ax, x \rangle > 0 => x^TAx > 0 $ $ \newline$ Пусть $y$ - произвольный веткор $\neq \theta => y^T X^T X y = (X y)^T (X y) = \langle Xy, Xy \rangle \geqslant 0 \langle Xy, Xy \rangle = 0 <=> Xy \equiv \theta$ т.к. $ y \neq \theta => $ столбцы $X$ линейно зависимы $=> X$ т.к. строк больше чем столбцов, матрица $X$ не может иметь полный ранг. Приходим к противоречию. Значит, $\langle Xy, Xy \rangle > 0$ и в силу произвольного выбора вектора $y$ матрица $X^T X$ положительно определена. А из этого следует, что $w = (X^TX)^{-1}X^TY $ является минимумом $Q(w)$

$$ \left(X^T X + \frac{N}{C}I\right)w = X^T y $$

Покажем, что матрица $ \left(X^T X + \frac{N}{C}I\right) $ положительно определена: $\newline$По определению, матрица $A$ положительно определена, если $ \forall x \neq \theta \langle Ax, x \rangle > 0 => x^TAx > 0 $ $ \newline$ Пусть $y$ - произвольный веткор $\neq \theta => y^T\left(X^T X + \frac{N}{C}I\right) y = y^TX^T X y + \frac{N}{C} y^T y = \langle Xy, Xy \rangle + \frac{N}{C} y^2 > 0 $ т.к. $$ \langle Xy, Xy \rangle \geqslant 0$$ $$ y \neq \theta => y^2 > 0 $$ Матрица $ \left(X^T X + \frac{N}{C}I\right) $ положительно определена. Из положительной определенности матрицы следует (по критерию Сильвестра), что все ее главные диагональные миноры положительны. Матрица невырождена, а значит обратима.

Точное решение: $$ w = \left(X^T X + \frac{N}{C}I\right)^{-1} X^T y $$

Докажем, что это минимум: $ \nabla_w(\nabla_w(L(w))) = \nabla_w\left((\frac{2}{N}X^T X + \frac{2}{C}I)w - \frac{2}{N} X^T y\right) = \frac{2}{N} X^T X + \frac{2}{C}I $

Как уже было показано ранее, такая матрица является положительно определенной, значит найденное решение является точкой минимума $L(w)$

Задача 4. Предсказываем вероятности.

Когда говорят о логистической регрессии, произносят фразу, что она "предсказывает вероятности положительного класса". Давайте разберемся, что же за этим стоит. Посчитаем математическое ожидание функции потерь и проверим, что предсказание алгоритма, оптимизирующее это мат. ожидание, будет являться вероятностью положительного класса.

И так, функция потерь на объекте $x_i$, который имеет метку $y_i \in \{0,1\}$ для предсказания $a(x_i)$ равна: $$L(y_i, b) =-[y_i == 1] \log a(x_i) - [y_i == 0] \log(1 - a(x_i)) $$

Где $[]$ означает индикатор $-$ он равен единице, если значение внутри него истинно, иначе он равен нулю. Тогда мат. ожидание при условии конкретного $x_i$ по определение мат. ожидания дискретной случайной величины: $$E(L | x_i) = -p(y_i = 1 |x_i ) \log a(x_i) - p(y_i = 0 | x_i) \log( 1 - a(x_i))$$

Подсказка: возможно, придется воспользоваться, что $p(y_i = 1 | x_i) + p(y_i = 0 | x_i) = 1$

Ваше решение здесь

$$ E(L | x_i) = -p(y_i = 1 |x_i ) \log a(x_i) - (1 - p(y_i = 1 | x_i)) \log( 1 - a(x_i))$$$$ p_i = p(y_i = 1 | x_i) $$$$ a_i = a(x_i) $$$$ E(L | x_i) = p_i \log(1 - a_i) - p_i \log a_i - \log(1 - a_i) = p_i \log\left(\frac{1 - a_i}{a_i}\right) - \log(1 - a_i) = f(a_i)$$

Найдем минимум этой функции $$ f_{a_i}' = -\frac{p_i}{(1 - a_i)a_i} + \frac{1}{1 - a_i} = 0 => a_i = p_i $$

При $ a_i < p_i $

$$ f_{a_i}' = \frac{a_i - p_i}{(1 - a_i)a_i} < 0 $$

т.к. $ 0 < a_i < 1 $

При $ a_i \geqslant p_i $

$$ f_{a_i}' = \frac{a_i - p_i}{(1 - a_i)a_i} \geqslant 0 $$

т.к. $ 0 < a_i < 1 $

Значит $ a(x_i) = p(y_i = 1 | x_i) $ точка минимума E(L | x_i)

Задача 5. Смысл регуляризации.

Нужно ли в L1/L2 регуляризации использовать свободный член $w_0$ (который не умножается ни на какой признак)?

Подсказка: подумайте, для чего мы вводим $w_0$

Ваше решение здесь

Нет, так как мы вводим его, чтобы сместить целевую переменную от нуля. Это смещение не должно штрафоваться

Реализация линейной модели (4 балла)

Зачем нужны батчи?

Как Вы могли заметить из теоретического введения, что в случае SGD, что в случа mini-batch GD, на каждой итерации обновление весов происходит только по небольшой части данных (1 пример в случае SGD, batch примеров в случае mini-batch). То есть для каждой итерации нам не нужна вся выборка. Мы можем просто итерироваться по выборке, беря батч нужного размера (далее 1 объект тоже будем называть батчом).

Легко заметить, что в этом случае нам не нужно загружать все данные в оперативную память, достаточно просто считать батч с диска, обновить веса, считать диска другой батч и так далее. В целях упрощения домашней работы, прямо с диска мы считывать не будем, будем работать с обычными numpy array.

Немножко про генераторы в Python

Идея считывания данных кусками удачно ложится на так называемые генераторы из языка Python. В данной работе Вам предлагается не только разобраться с логистической регрессией, но и познакомиться с таким важным элементом языка. При желании Вы можете убрать весь код, связанный с генераторами, и реализовать логистическую регрессию и без них, штрафоваться это никак не будет. Главное, чтобы сама модель была реализована правильно, и все пункты были выполнены.

Подробнее можно почитать вот тут https://anandology.com/python-practice-book/iterators.html

К генератору стоит относиться просто как к функции, которая порождает не один объект, а целую последовательность объектов. Новое значение из последовательности генерируется с помощью ключевого слова yield. Ниже Вы можете насладиться генератором чисел Фибоначчи.

Вот так можно сгенерировать последовательность Фибоначчи.

Заметьте, что к генераторам можно применять некоторые стандартные функции из Python, например enumerate.

Пересоздавая объект, можно сколько угодно раз генерировать заново последовательность.

А вот так уже нельзя.

Концепция крайне удобная для обучения моделей $-$ у Вас есть некий источник данных, который Вам выдает их кусками, и Вам совершенно все равно откуда он их берет. Под ним может скрывать как массив в оперативной памяти, как файл на жестком диске, так и SQL база данных. Вы сами данные никуда не сохраняете, оперативную память экономите.

Если Вам понравилась идея с генераторами, то Вы можете реализовать свой, используя прототип batch_generator. В нем Вам нужно выдавать батчи признаков и ответов для каждой новой итерации спуска. Если не понравилась идея, то можете реализовывать SGD или mini-batch GD без генераторов.

Запустите обе регрессии на синтетических данных.

Выведите полученные веса и нарисуйте разделяющую границу между классами (используйте только первых два веса для первых двух признаков X[:,0], X[:,1] для отображения в 2d пространство ).

Далее будем анализировать Ваш алгоритм. Для этих заданий используйте датасет ниже.

Покажите сходимости обеих регрессией на этом датасете: изобразите график функции потерь, усредненной по $N$ шагам градиентого спуска, для разных alpha (размеров шага). Разные alpha расположите на одном графике.

$N$ можно брать 10, 50, 100 и т.д.

Что Вы можете сказать про сходимость метода при различных alpha? Какое значение стоит выбирать для лучшей сходимости?

Изобразите график среднего значения весов для обеих регрессий в зависимости от коеф. регуляризации С из np.logspace(3, -3, 10)

Довольны ли Вы, насколько сильно уменьшились Ваши веса?

Боевое применение (4 балла)

Защита данной части возможна только при преодолении в проекте бейзлайна Handmade baseline.

Давайте применим модель на итоговом проекте! Датасет сделаем точно таким же образом, как было показано в project_overview.ipynb

Применим обе регрессии, подберем для них параметры и сравним качество. Может быть Вы еще одновременно с решением домашней работы подрастете на лидерборде!

Подберите размер батча для обучения. Линейная модель не должна учиться дольше нескольких минут.

Не забывайте использовать скейлер!

Разбейте данные на обучение и валидацию. Подберите параметры C, alpha, max_epoch, model_type на валидации (Вы же помните, как правильно в этой задаче делать валидацию?)

Подберите порог линейной модели, по достижении которого, Вы будете относить объект к классу 1. Вспомните, какую метрику мы оптимизируем в соревновании. Как тогда правильно подобрать порог?

С лучшими параметрами на валидации сделайте предсказание на тестовом множестве, отправьте его на проверку на платформу kaggle. Убедитесь, что Вы смогли побить public score первого бейзлайна.

При сдаче домашки Вам необходимо кроме ссылки на ноутбук показать Ваш ник на kaggle, под которым Вы залили решение, которое побило Handmade baseline.

Ilya Alkisev

Фидбек (бесценно)

Ваше ответ здесь

ВАШ ОТЗЫВ ЗДЕСЬ